The present invention relates to a process for associating data with ATM cells reaching an item of ATM network equipment via virtual connections.
It is known that in ATM ("asynchronous transfer mode") technology, virtual connections are established between the items of equipment attached to the network, within the physical links which exist between these items of equipment. Each virtual connection is designated by a pair of identifiers which are retrieved from specified fields of the header of each cell transmitted over this virtual connection:
a virtual path identifier, or VPI, which generally designates resources allocated in a semi-permanent manner; PA1 a virtual channel identifier, or VCI, which designates resources allocated dynamically within the virtual paths. PA1 the bits of the VPI field that are used be contiguous; PA1 the bits of the VPI field that are used be the least significant bits of the VPI field (starting from bit 5 of byte 2 of the cell header); PA1 the bits of the VCI field that are used be contiguous; PA1 the bits of the VCI field that are used be the least significant bits of the VCI field (starting from bit 5 of byte 4 of the cell header); PA1 the non-assigned bits, that is to say those not used by the user or by the network in the 28-bit routing field, be set to 0.
The switching equipment of the ATM network carries out the routing of each packet, or cell, on the basis of one or other (or both) of the VPI-VCI identifiers read from its header.
According to the applicable standards (ITU-T Recommendation I.361), the VCI is composed of L.sub.c =16 bits, and the VPI is composed of L.sub.p =8 bits at a user-network interface (UNI) and of L.sub.p =12 bits at a network node interface (NNI). ITU-T Recommendation I.361 further prescribes, in paragraphs 2.2.3 and 2.3.2, that:
The coding of the VPI-VCI pairs permits the differentiation of 2.sup.28, i.e. more than two hundred and sixty million virtual connections within each physical link. In practice, operators only use a much smaller number of virtual connections (typically of the order of 4,000).
Since the cells pertaining to the established virtual connections reach the equipment of the network randomly and at a very high rate, this equipment must be capable, on the basis of the VPI-VCI pairs read from the header of the cells, of very rapidly associating data with cells so as to adopt an appropriate response.
The simplest way of doing this would be to use a random access memory (RAM) where the data would be stored at addresses specified by the VPI-VCI pairs. However, the cost of the memory with a 28-bit index would be prohibitive for a derisory return when only a few thousand virtual connections are active.
Another approach is to use a dichotomy search, requiring a search loop, whose execution time is logarithmic as a function of the number of records, in a table in which the records are ranked in increasing or decreasing order of the VPI-VCI keys. In the context of ATM network equipment, this approach requires extremely fast electronics.
It is also possible to envisage using, as in EP-A-0 600 683, associative or contents-addressable memories (CAM). This solution has the drawback of being bulky and very expensive.
Within the realm of computer programming, a hashing technique is commonly used for the fast lookup of translation tables, as for example for databases or language compilers (see Knuth: "The Art of Computer Programming", Vol. 3, Addison-Wesley 1973, pages 506-542). This technique relies on the use of a hash function which randomly reduces the long access key into a shorter code, termed the H code. The purpose of this random function is to spread the H codes evenly over a reduced random access range. One example, derived from the cyclic code technique, of a usable function relies on polynomial division (see R. Jain: "A Comparison of Hashing Schemes for Address Lookup in Computer Networks", IEEE Trans. on Communications, Vol. 40, No. 10, October 1992, pages 1570-1573). Conflicts arise when the same H code is associated with several different access keys. These conflicts are resolved by a routine for searching through secondary overflow strings, which makes it possible to retain a very short mean execution time for the search. However, as noted in the aforesaid work by Knuth (page 540), hashing methods are only efficient on average, and the search time may be very long in unfavourable cases. This is due to the fact that the duration of a search through the secondary strings in the case of conflict is not bounded. These methods therefore appear to be unusable for the problem of the real-time association of data with ATM cells, since the execution time for the search must remain less than a cell time in order for the bit rate specifications to be complied with.
An object of the present invention is to propose an efficient and economic search procedure for associating data with ATM cells.